package 二分查找;
/**
 * 
* @ClassName: BinarySearch 
* @Description: TODO(二分查找,折半查找) 
* @author xiaok 
* @date 2018年10月5日 下午3:40:00 
*
 *
	二分查找变种
 *
 * 二分查找可以有很多变种，实现变种要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下：
 *
 * public int binarySearch(int[] nums, int key) {
 *     int l = 0, h = nums.length - 1;
 *     while (l < h) {
 *         int m = l + (h - l) / 2;
 *         if (nums[m] >= key) {
 *             h = m;
 *         } else {
 *             l = m + 1;
 *         }
 *     }
 *     return l;
 * }
 * Copy to clipboardErrorCopied
 * 该实现和正常实现有以下不同：
 *
 * h 的赋值表达式为 h = m
 * 循环条件为 l < h
 * 最后返回 l 而不是 -1
 * 在 nums[m] >= key 的情况下，可以推导出最左 key 位于 [l, m] 区间中，这是一个闭区间。h 的赋值表达式为 h = m，因为 m 位置也可能是解。
 *
 * 在 h 的赋值表达式为 h = m 的情况下，如果循环条件为 l <= h，那么会出现循环无法退出的情况，因此循环条件只能是 l < h。以下演示了循环条件为 l <= h 时循环无法退出的情况：
 *
 * nums = {0, 1, 2}, key = 1
 * l   m   h
 * 0   1   2  nums[m] >= key
 * 0   0   1  nums[m] < key
 * 1   1   1  nums[m] >= key
 * 1   1   1  nums[m] >= key
 * ...
 * Copy to clipboardErrorCopied
 * 当循环体退出时，不表示没有查找到 key，因此最后返回的结果不应该为 -1。为了验证有没有查找到，需要在调用端判断一下返回位置上的值和 key 是否相等。
 */
public class BinarySearch {

	/**
	 * 使用递归的二分查找
	 *title:recursionBinarySearch
	 *@param arr 有序数组
	 *@param key 待查找关键字
	 *@return 找到的位置
	 */
	public static int recursionBinarySearch(int[] arr,int key,int low,int high){
		
		if(key < arr[low] || key > arr[high] || low > high){
			return -1;				
		}
		
		//int middle = (low + high) / 2;			//初始中间位置
		int middle = low + ( high - low )/2;
		if(arr[middle] > key){
			//比关键字大则关键字在左区域
			return recursionBinarySearch(arr, key, low, middle - 1);
		}else if(arr[middle] < key){
			//比关键字小则关键字在右区域
			return recursionBinarySearch(arr, key, middle + 1, high);
		}else {
			return middle;
		}	
		
	}
	/**
	 * 不使用递归的二分查找
	 *title:commonBinarySearch
	 *@param arr
	 *@param key
	 *@return 关键字位置
	 */
	public static int commonBinarySearch(int[] arr,int key){
		int low = 0;
		int high = arr.length - 1;
		int middle = 0;			//定义middle
		
		if(key < arr[low] || key > arr[high] || low > high){
			return -1;				
		}
		
		while(low <= high){
			//middle = (low + high) / 2;
			 middle = low + ( high - low )/2;
			if(arr[middle] > key){
				//比关键字大则关键字在左区域
				high = middle - 1;
			}else if(arr[middle] < key){
				//比关键字小则关键字在右区域
				low = middle + 1;
			}else{
				return middle;
			}
		}
		
		return -1;		//最后仍然没有找到，则返回-1
	}

	public static void main(String[] args) {
		 
		int[] arr = {1,3,5,7,9,11,18,111,222,666,7777,123131};
		int key = 123131;
		//int position = recursionBinarySearch(arr,key,0,arr.length - 1);
		
		int position = commonBinarySearch(arr, key);
 
              if(position == -1){
			System.out.println("查找的是"+key+",序列中没有该数！");
		}else{
			System.out.println("查找的是"+key+",找到位置为："+position);
		}
		
	}

	
}
